package com.zxy.javaarithmetic.tree;

/**
 * 小顶堆
 */
public class MinHeap {
    private int[] mHeap;

    //从1开始存储
    private int count;
    private int size;

    public MinHeap(int size) {
        count = 0;
        this.size = size;
        mHeap = new int[size + 1];
    }

    public void insert(int val) {
        //堆已满
        if (count == size) return;
        //第一个数是从下标1开始存储的
        mHeap[++count] = val;

        //由下而上堆化
        int i = count;
        while ((i / 2) > 0 && mHeap[i] < mHeap[i / 2]) {
            swap(i, i / 2);
            i /= i;
        }
    }

    private void swap(int i, int j) {
        int tmp = mHeap[i];
        mHeap[i] = mHeap[j];
        mHeap[j] = tmp;
    }

    public int getMin() {
        if (count == 0) return Integer.MIN_VALUE;
        int min = mHeap[1];
        mHeap[1] = mHeap[count--];

        //自上而下堆化
        int i = 1;
        int minPos;
        while (true) {
            minPos = i;
            if (2 * i <= count && mHeap[2 * i] < mHeap[i]) minPos = 2 * i;
            if ((2 * i + 1) <= count && mHeap[2 * i + 1] < mHeap[minPos]) minPos = 2 * i + 1;
            if (minPos == i) break;
            swap(i, minPos);
            i = minPos;
        }
        return min;
    }

}
